
uint32_t ip;

typedef struct inode_s inode_t;

struct inode_s {
  inode_t *l;
  inode_t *r;
};

typedef struct lnode_s lnode_t;

struct lnode_s {
  inode_t *l;
  inode_t *r;
  uchar_t *region;
}

inode_t tree;

void
jade_add_region(uint32_t ip, uint32_t count, uchar_t *region)
{
  uint32 i;
  inode_t *p = &tree;
  inode_t **pp = &p;

  for (i = 31; i >= 32 - count; i--)
  {
    if (!*pp) {
      *pp = malloc(sizeof(inode_t));
      p = *pp;
      p->l = NULL;
      p->r = NULL;
    }

    p = *pp;

    if ((ip >> i) & 0x1) {
      pp = &p->r;
    }
    else {
      pp = &p->l;
    }
  }

  if (!*pp) {
    lnode_t *leaf = malloc(sizeof(lnode_t));
    *pp = leaf;
    leaf->l = NULL;
    leaf->r = NULL;
    leaf->region = region;
  }
}

uchar_t *
jade_find_region(uint32_t ip)
{
  uint32_t i;
  inode_t *p = &tree;

  for (i = 31; i >= 0; i--) {
    if ((ip >> i) & 0x1) {
      p = p->r;
    } else {
      p = p->l;
    }

    if (!p->l && !p->r) {
      lnode_t *leaf = p;
      return leaf->region;
    }
  }

  return NULL;
}